/**
 * 双向链表模块。
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */
module system.collections.LinkedList;

import system.Exception;
import system.Traits;
import system.collections.IEnumerator;
import system.collections.IEnumerable;
import system.collections.ICollection;
import system.collections.EqualityComparer;
import system.collections.IList;
import system.collections.objectmodel.ReadOnlyListCollection;

version(unittest)
{
	import system.collections.ArrayList; //only for unit test
}


/**
 * 表示 LinkedList(T) 中的节点。无法继承此类。
 * Comments: LinkedList(T) 集合的每个元素都是 LinkedListNode(T)。
 *           LinkedListNode(T) 包含一个值，对其所属的 LinkedList(T) 引用，
 *           对前一个节点的引用以及对后一个节点的引用。
 */
public final class LinkedListNode(T)
{
	package T theItem;
	package LinkedList!(T) theList;
	package LinkedListNode!(T) thePrevious;
	package LinkedListNode!(T) theNext;

	/**
	 * 初始化 LinkedListNode(T) 类的新实例，该实例包含指定的值。
	 * Comments: list、next 和 previous 属性都设置为 null。
	 */
	public this( T value )
	{
		theItem = value;
	}

	package this( LinkedList!(T) list, T value )
	{
		theList = list;
		theItem = value;
	}

	/**
	 * 获取 LinkedListNode(T) 所属的 LinkedList(T)。
	 * Comments: 如果 LinkedListNode(T) 未链接，则为 null。
	 */
	public LinkedList!(T) list()
	{
		return theList;
	}

	/**
	 * 获取 LinkedList(T) 中的前一个节点。
	 * Comments: 如果当前节点是 LinkedList(T) 的第一个元素 (First)，则为 null。
	 */
	public LinkedListNode!(T) previous()
	{
		if( (theList !is null) && (this !is theList.theFirst) )
		{
			return thePrevious;
		}
		return null;
	}
	/**
	 * 获取 LinkedList(T) 中的后一个节点。
	 * Comments: 如果当前节点是 LinkedList(T) 的最后一个元素 (Last)，则为 null。
	 */
	public LinkedListNode!(T) next()
	{
		if( (theList !is null) && ( theNext !is theList.theFirst) )
		{
			return theNext;
		}
		return null;
	}

	/**
	 * 获取节点中包含的值。
	 */
	public T value()
	{
		return theItem;
	}
	/**
	 * 设置节点中包含的值。
	 */
	public void value(T otherValue)
	{
		theItem = otherValue;
	}
}

/**
 * 表示双向链表。
 * Comments: LinkedList(T) 为通用链表。
 *
 *           LinkedList(T) 提供 LinkedListNode(T) 类型的单独节点，
 *           因此插入和移除的运算复杂度为 O(1)。
 *
 *           可以移除节点，然后在同一列表或其他列表中重新插入它们，
 *           这样在堆中便不会分配额外的对象。
 *
 *           由于该列表还维护内部计数，因此获取 count 属性的运算复杂度为 O(1)。
 *
 *           由于 LinkedList(T) 是双向链表，因此每个节点向前指向 next 节点，向后指向 previous 节点。
 *
 *           如果节点及其值是同时创建的，则包含引用类型的列表性能会更好。
 *           LinkedList(T) 接受 null 作为引用类型的有效 Value 属性，并且允许重复值。
 *
 *           如果 LinkedList(T) 为空，则 first 和 last 属性为 null。
 *
 *           LinkedList(T) 类不支持使列表处于不一致状态的链接、拆分、循环或其他功能。
 *           在单个线程上列表保持一致。
 *           LinkedList(T) 支持的唯一多线程方案是多线程读取操作。
 */
public class LinkedList(T) : IList!(T), ICollection!(T), IEnumerable!(T)
{
	private int theSize;
	private int theVersion;
	/*
	 * 内部使用双向循环链表。
	 * 在内部 last.theNext is first
	 * 在外部 last.next is null
	 */
	package LinkedListNode!(T) theFirst;

	/**
	 * 初始化为空的 LinkedList(T) 类的新实例。
	 * Comments: LinkedList(T) 接受 null 作为引用类型的有效 value，并且允许重复值。
	 *           如果 LinkedList(T) 为空，则 first 和 last 属性为 null。
	 *           此构造函数的运算复杂度为 O(1)。
	 */
	public this()
	{
	}

	/**
	 * 初始化 LinkedList(T) 类的新实例。
	 * 该实例包含从指定的 IEnumerable(T) 中复制的元素并且其容量足以容纳所复制的元素数。
	 * Comments: ditto。
	 */
	public this(IEnumerable!(T) collection)
	in
	{
		assert( collection !is null );
	}
	body
	{
		foreach(item; collection)
		{
			addLast(item);
		}
	}

	/**
	 * 验证已被引用的节点。
	 */
	private void validateNode(LinkedListNode!(T) node)
	{
		assert( node !is null );
		assert( node.theList is this );
	}
	/*
	 * 验证新节点。
	 */
	private void validateNewNode(LinkedListNode!(T) newNode)
	{
		assert( newNode !is null );
		assert( newNode.theList is null );
	}

	/*
	 * 把 newNode 插入到 node 的前面。
	 */
	private void insertBefore(LinkedListNode!(T) node, LinkedListNode!(T) newNode)
	{
		newNode.theNext = node;
		newNode.thePrevious = node.thePrevious;

		node.thePrevious.theNext = newNode;
		node.thePrevious = newNode;

		theSize++;
		theVersion++;
	}

	/*
	 * 插入新节点到空链表。
	 */
	private void insertToEmptyList(LinkedListNode!(T) newNode)
	{
		newNode.theNext = newNode;
		newNode.thePrevious = newNode;
		theFirst = newNode;
		theSize++;
		theVersion++;
	}

	/*
	 * 通过索引获得节点。
	 */
	private LinkedListNode!(T) getNode(int index)
	{
		LinkedListNode!(T) node;

		if( index < (theSize / 2) )
		{
			node = theFirst;
			for(auto i = 0; i < index; i++)
			{
				node = node.theNext;
			}
		}
		else
		{
			node = theFirst.thePrevious;
			for(auto i = theSize-1; i > index; i--)
			{
				node = node.thePrevious;
			}
		}
		return node;
	}

	/* **************************************************************
	 * 双向循环链表特有操作。
	 * **************************************************************/

	/**
	 * 在 LinkedList(T) 中指定的现有节点后添加包含指定值的新节点。
	 * Params: node = 要在其后插入包含 value 的新 LinkedListNode(T) 的 LinkedListNode(T)。
	 *         value = 要添加到 LinkedList(T) 的值。
	 * Returns: 包含 value 的新 LinkedListNode(T)。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final LinkedListNode!(T) addAfter(LinkedListNode!(T) node, T value)
	in
	{
		validateNode(node);
	}
	body
	{
		auto newNode = new LinkedListNode!(T)(node.theList, value);
		this.insertBefore(node.theNext, newNode);
		return newNode;
	}

	/**
	 * 在 LinkedList(T) 中指定的现有节点后添加指定的新节点。
	 * Params: node = 要在其后插入包含 value 的新 LinkedListNode(T) 的 LinkedListNode(T)。
	 *         newNode = 要添加到 LinkedList(T) 的新 LinkedListNode(T)。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final void addAfter(LinkedListNode!(T) node, LinkedListNode!(T) newNode)
	in
	{
		validateNode(node);
		validateNewNode(newNode);
	}
	body
	{
		this.insertBefore(node.theNext, newNode);
		newNode.theList = this;
	}

	/**
	 * 在 LinkedList(T) 中指定的现有节点前添加包含指定值的新节点。
	 * Params: node = 要在其前插入包含 value 的新 LinkedListNode(T) 的 LinkedListNode(T)。
	 *         value = 要添加到 LinkedList(T) 的值。
	 * Returns: 包含 value 的新 LinkedListNode(T)。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final LinkedListNode!(T) addBefore(LinkedListNode!(T) node, T value)
	in
	{
		validateNode(node);
	}
	body
	{
		auto newNode = new LinkedListNode!(T)(node.theList, value);
		this.insertBefore(node, newNode);

		/*
		 * 判断是否在第一个节点前增加新节点。
		 * 如果是，把新节点作为第一个节点。
		 */
		if( node is theFirst )
		{
			theFirst = newNode;
		}

		return newNode;
	}

	/**
	 * 在 LinkedList(T) 中指定的现有节点前添加指定的新节点。
	 * Params: node = 要在其前插入 newNode 的 LinkedListNode(T)。
	 *         newNode = 要添加到 LinkedList(T) 的新 LinkedListNode(T)。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final void addBefore(LinkedListNode!(T) node, LinkedListNode!(T) newNode)
	in
	{
		validateNode(node);
		validateNewNode(newNode);
	}
	body
	{
		this.insertBefore(node, newNode);
		newNode.theList = this;

		if( node is theFirst )
		{
			theFirst = newNode;
		}
	}

	/**
	 * 在 LinkedList(T) 的开头处添加指定的新节点。
	 * Params: node = 要在 LinkedList(T) 的开头处添加的新 LinkedListNode(T)。
	 */
	public final void addFirst(LinkedListNode!(T) node)
	in
	{
		validateNewNode(node);
	}
	body
	{
		if( theFirst is null )
		{
			this.insertToEmptyList(node);
		}
		else
		{
			this.insertBefore(theFirst, node);
			theFirst = node;
		}

		node.theList = this;
	}

	/**
	 * 在 LinkedList(T) 的开头处添加包含指定值的新节点。
	 * Params: value = 要在 LinkedList(T) 的开头处添加的值。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final LinkedListNode!(T) addFirst(T value)
	{
		auto newNode = new LinkedListNode!(T)(this, value);

		if( theFirst is null )
		{
			this.insertToEmptyList(newNode);
			return newNode;
		}
		else
		{
			this.insertBefore(theFirst, newNode);
			theFirst = newNode;
			return newNode;
		}
	}

	/**
	 * 在 LinkedList(T) 的结尾处添加指定的新节点。
	 * Params: node = 要添加至 LinkedList(T) 结尾的新 LinkedListNode(T)。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final void addLast(LinkedListNode!(T) node)
	in
	{
		validateNewNode(node);
	}
	body
	{
		if( theFirst is null )
		{
			this.insertToEmptyList(node);
		}
		else
		{
			this.insertBefore(theFirst, node);
		}

		node.theList = this;
	}
	/**
	 * 在 LinkedList(T) 的结尾处添加包含指定值的新节点。
	 * Params: value = 要添加到 LinkedList(T) 的末尾的值。
	 * Returns: 包含 value 的新 LinkedListNode(T)。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final LinkedListNode!(T) addLast(T value)
	{
		auto newNode = new LinkedListNode!(T)(this, value);
		if(theFirst is null)
		{
			this.insertToEmptyList(newNode);
			return newNode;
		}
		else
		{
			this.insertBefore(theFirst, newNode);
			return newNode;
		}
	}

	/**
	 * 查找包含指定值的第一个节点。
	 * Params: value = 要在 LinkedList(T) 中定位的值。
	 * Returns: 如果找到，则为包含指定值的第一个 LinkedListNode(T)；否则为 null。
	 * Comments: 在 LinkedList(T) 中从 first 处开始向前搜索，并在 last 处结束搜索。
	 *           此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 *
	 *           使用此方法的引用类型和值类型最好重载 opEquals，opCmp 和 toHash。
	 */
	public final LinkedListNode!(T) find(T value)
	{
		auto node = theFirst;
		if( node !is null )
		{
			static if( IsReferenceType!(T) )
			{
				auto comparer = DefaultEqualityComparer!(T).getInstance();
				if( value !is null )
				{
					do
					{
						if( comparer.equals(value, node.theItem) )
						{
							return node;
						}
						node = node.theNext;
					}
					while(node !is theFirst);
				}
				else
				{
					do
					{
						if( node.theItem is null )
						{
							return node;
						}
						node = node.theNext;
					}
					while(node !is theFirst);
				}
			}
			else
			{
				do
				{
					if( value == node.theItem )
					{
						return node;
					}
					node = node.theNext;
				}
				while(node !is theFirst);
			}
		}

		return null;
	}

	/**
	 * 查找包含指定值的最后一个节点。
	 * Params: value = 要在 LinkedList(T) 中定位的值。
	 * Returns: 如果找到，则为包含指定值的最后一个 LinkedListNode(T)；否则为 null。
	 * Comments: 在 LinkedList(T) 中从 last 处开始向后搜索，并在 first 处结束搜索。
	 *           此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 *
	 *           使用此方法的引用类型和值类型最好重载 opEquals，opCmp 和 toHash。
	 */
	public final LinkedListNode!(T) findLast(T value)
	{
		if( theFirst !is null )
		{
			auto prev = theFirst.thePrevious;
			auto node = prev;
			if( node !is null )
			{
				static if( IsReferenceType!(T) )
				{
					auto comparer = DefaultEqualityComparer!(T).getInstance();
					if(value !is null)
					{
						do
						{
							if( comparer.equals(value, node.theItem) )
							{
								return node;
							}

							node = node.thePrevious;
						}
						while(node !is prev);
					}
					else
					{
						do
						{
							if( node.theItem is null )
							{
								return node;
							}

							node = node.thePrevious;
						}
						while(node !is prev);
					}
				}
				else
				{
					do
					{
						if( value == node.theItem )
						{
							return node;
						}

						node = node.thePrevious;
					}
					while(node !is prev);
				}
			}
		}

		return null;
	}

	/**
	 * 从 LinkedList(T) 中移除指定的节点。
	 * Params: node = 要从 LinkedList(T) 移除的 LinkedListNode(T)。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final void remove(LinkedListNode!(T) node)
	in
	{
		validateNode(node);
	}
	body
	{
		/*
		 * 判断是否只剩一个节点。
		 */
		if( node.theNext is node )
		{
			theFirst = null;
		}
		else
		{
			node.theNext.thePrevious = node.thePrevious;
			node.thePrevious.theNext = node.theNext;
			if(theFirst is node)
			{
				theFirst = node.theNext;
			}
		}

		node.theList = null;
		node.thePrevious = null;
		node.theNext = null;

		theSize--;
		theVersion++;
	}

	/**
	 * 移除位于 LinkedList(T) 开头处的节点。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final void removeFirst()
	{
		if( theFirst !is null )
		{
			this.remove(theFirst);
		}
	}

	/**
	 * 移除位于 LinkedList(T) 结尾处的节点。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final void removeLast()
	{
		if( theFirst !is null )
		{
			this.remove(theFirst.thePrevious);
		}
	}

	/**
	 * 获取 LinkedList(T) 的第一个节点。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final LinkedListNode!(T) first()
	{
		return theFirst;
	}

	/**
	 * 获取 LinkedList(T) 的最后一个节点。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final LinkedListNode!(T) last()
	{
		if( theFirst !is null )
		{
			return theFirst.thePrevious;
		}

		return null;
	}

	/* ********************************************************
	 * 实现 IEnumerable(T) 接口。
	 * ********************************************************/

	public final Enumerator getEnumerator()
	{
		return new Enumerator(this);
	}

	public final int opApply(int delegate(ref T value) dg)
	{
		auto scope enumerator = new Enumerator(this);
        int result = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(value) ) != 0 )
				break;
		}
		return result;
	}

	public final class Enumerator : IEnumerator!(T)
	{
		private LinkedList!(T) theList;
		private LinkedListNode!(T) theCurrent;
		private int theIndex;
		private int theVersion;

		package this(LinkedList!(T) list)
		{
			this.theList = list;
			this.theVersion = list.theVersion;
			this.theIndex = -1;
		}

		public bool moveNext()
		{
			if( theVersion != theList.theVersion )
				throw new InvalidOperationException("Enumerate failed, because list was be modified.");

			if( theCurrent is null )
			{
				theCurrent = theList.theFirst;
			}
			else
			{
				theCurrent = theCurrent.theNext;
				if( theCurrent is theList.theFirst )
				{
					theCurrent = null;
				}
			}

			/*
			 * 链表是否为空或已遍历完毕。
			 */
			if( theCurrent is null )
			{
				theIndex = -1;
				return false;
			}

			theIndex++;
			return true;
		}

		public T current()
		{
			if( theIndex == -1 )
				throw new InvalidOperationException();
			return theCurrent.theItem;
		}

		public void reset()
		{
			if( theVersion != theList.theVersion )
				throw new InvalidOperationException();
			theCurrent = null;
			theIndex = -1;
		}
	}

	/* **********************************************************
	 * 实现 ICollection(T) 接口
	 * **********************************************************/

	/**
	 * 查看链表是否为空。
	 */
	public final bool isEmpty()
	{
		return theFirst is null;
	}

	/**
	 * 获取 LinkedList(T) 中实际包含的节点数。
	 * Comments: 此方法的运算复杂度为 O(1)。
	 */
	public final int count()
	{
		return theSize;
	}

	/**
	 * 查看链表是否只读。
	 */
	public final bool isReadOnly()
	{
		return false;
	}

	/**
	 * 添加指定的元素到链表中。
	 */
	public bool add(T item)
	{
		this.addLast(item);
		return true;
	}

	/**
	 * 从 LinkedList(T) 中移除所有节点。
	 * Comments: count 被设置为零，并且集合中的元素对其他对象的引用也被释放。
	 *           first 和 last 被设置为 null。
	 *           此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final void clear()
	{
		theFirst = null;
		theSize = 0;
		theVersion++;
	}

	/**
	 * 确定某值是否在 LinkedList(T) 中。
	 * Params: item = 要在 LinkedList(T) 中定位的值。对于引用类型，该值可以为 null。
	 * Returns: 如果在 LinkedList(T) 中找到则为 true；否则为 false。
	 * Comments: 此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final bool contains(T item)
	{
		return this.find(item) !is null;
	}

	/**
	 * 将整个 LinkedList(T) 复制到一维 Array。
	 * Params: array = 作为从 LinkedList(T) 复制元素的一维 Array。
	 * Comments: 此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final void toArray(T[] array)
	in
	{
		assert( array !is null );
	}
	body
	{
	    auto node = theFirst;
		if( node !is null )
		{
			for(auto i = 0; i < theSize; i++)
			{
				array[i] = node.theItem;
				node = node.theNext;
			}
		}
	}

	/**
	 * 从 LinkedList(T) 中移除指定值的第一个匹配项。
	 * Params: item = 要从 (T) 中移除的值。
	 * Returns: 如果成功移除包含 value 的元素，则为 true；否则为 false。
	 *          如果在原始 LinkedList(T) 中没有找到 value，此方法也会返回 false。
	 * Comments: 此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 */
	public final bool remove(T item)
	{
		auto node = this.find(item);
		if( node is null )
		{
			return false;
		}
		this.remove(node);
		return true;
	}

	/* **************************************************************
	 * 实现 IList(T) 接口。
	 * **************************************************************/

	/**
	 * 获取指定索引处的元素。
	 * Params: index = 要获得的元素从零开始的索引。
	 *         索引值必须小于 count 。
	 * Throws: InvalidOperationException，当链表为空时。
	 * Comments: LinkedList(T) 接受 null 作为引用类型的有效值并且允许有重复的元素。
	 *           通过使用下面的语法，此属性提供了访问集合中特定元素的能力：list[index]。
	 *           检索此属性值的运算复杂度为 O(n)；
	 */
	public final T opIndex(int index)
	in
	{
		assert( index >= 0 && index < theSize );
	}
	body
	{
		if( theFirst is null )
		{
			throw new InvalidOperationException("The list is empty.");
		}

		return this.getNode(index).theItem;
	}

	/**
	 * 设置指定索引处的元素。
	 * Params: index = 要获得的元素从零开始的索引。
	 *         索引值必须小于 count 。
	 *         item = 要设置的元素值。
	 * Throws: InvalidOperationException，当链表为空时。
	 * Comments: LinkedList(T) 接受 null 作为引用类型的有效值并且允许有重复的元素。
	 *           通过使用下面的语法，此属性提供了设置集合中特定元素的能力：list[index] = item。
	 *           设置此属性值的运算复杂度为 O(n)；
	 */
	public final void opIndexAssign(T item, int index)
	in
	{
		assert( index >= 0 && index < this.theSize );
	}
	body
	{
		if( theFirst is null )
		{
			throw new InvalidOperationException("The list is empty.");
		}

		this.getNode(index).theItem = item;
		this.theVersion++;
	}

	/**
	 * 搜索指定的对象，并返回整个 LinkedList(T) 中第一个匹配项的从零开始的索引。
	 * Params: item = 要在 LinkedList(T) 中定位的对象。对于引用类型，该值可以为 null 。
	 * Returns: 如果在整个 LinkedList(T) 中找到 item 的第一个匹配项，则为该项的从零开始的索引；否则为 -1。
	 * Comments: 从 LinkedList(T) 的第一个元素开始向前搜索，到最后一个元素停止搜索。
	 *           此方法执行线性搜索；因此，此方法的运算复杂度为 O(n)，其中 n 是 count。
	 *
	 *           使用此方法的引用类型和值类型最好重载 opEquals，opCmp 和 toHash。
	 */
	public final int indexOf(T item)
	{
		if( theFirst !is null )
		{
			LinkedListNode!(T) node = theFirst;
			static if( IsReferenceType!(T) )
			{
				if( item !is null )
				{
					auto comparer = DefaultEqualityComparer!(T).getInstance();
					for(auto i = 0; i < theSize; i++)
					{
						if( comparer.equals(item, node.theItem) )
						{
							return i;
						}
						node = node.theNext;
					}
				}
				else
				{
					for(auto i = 0; i < theSize; i++)
					{
						if( node.theItem is null )
						{
							return i;
						}
						node = node.theNext;
					}
				}
			}
			else
			{
				for(auto i = 0; i < theSize; i++)
				{
					if( item == node.theItem )
					{
						return i;
					}
					node = node.theNext;
				}
			}
		}

		return -1;
	}

	/**
	 * 将元素插入 LinkedList(T) 的指定索引处。
	 * Params: index = 从零开始的索引，应在该位置插入 item。
	 *         item = 要插入的对象。对于引用类型，该值可以为 null 。
	 * Comments: LinkedList(T) 接受 null 作为引用类型的有效值并且允许有重复的元素。
	 *           如果 index 等于 0，而链表又为空或者如果 index 等于 count，
	 *           则将 item 添加到 LinkedList(T) 的结尾处。
	 *           此时方法的时间复杂度为O(1)。
	 *           其他情况的时间复杂度为 O(n)。
	 */
	public final void insert(int index, T item)
	in
	{
		assert( index >= 0 && index <= this.theSize );
	}
	body
	{
		if( (index == 0 && theFirst is null)  || index == theSize)
		{
			this.addLast(item);
		}
		else
		{
			this.getNode(index).theItem = item;
		}
		this.theVersion++;
	}

	/**
	 * 移除 LinkedList(T) 指定索引处的元素。
	 * Params: index = 要移除的元素的从零开始的索引。
	 * Comments: 在链表非空的情况下，此方法的时间复杂度为O(n)。
	 */
	public final void removeAt(int index)
	in
	{
		assert( index >= 0 && index < this.theSize );
	}
	body
	{
		if( theFirst !is null )
		{
			this.remove( getNode(index) );
		}
	}

	/**
	 * 返回当前集合的只读 IList(T) 包装。
	 * Returns: 作为当前 LinkedList(T) 周围的只读包装的 ReadOnlyListCollection(T)。
	 * Comments: 若要防止对 LinkedList(T) 的任何修改，应该仅通过此包装公开 LinkedList(T)。
	 *           只读集合只是一个具有用于防止修改的包装的集合；因此，如果更改基础集合，则只读集合将反映那些更改。
	 *           此方法的运算复杂度是 O(1)。
	 */
	public final ReadOnlyListCollection!(T) asReadOnly()
	{
		return new ReadOnlyListCollection!(T)(this);
	}
}

unittest
{
	LinkedList!(int) intList;
	LinkedList!(string) stringList;

	intList = new LinkedList!(int)();
	intList.add(3);
	intList.addLast(4);
	intList.addFirst(2);

	auto strList = new ArrayList!(string)(3);
	strList.add("I");
	strList.add("love");
	strList.add("you");

	stringList = new LinkedList!(string)(strList);

	void addedTest()
	{
		auto i = 2;
		foreach(current; intList)
		{
			assert( current == i );
			i++;
		}

		assert(i == 5);
	}

	addedTest();

	void createdTest()
	{
		auto i = 0;
		foreach(current; stringList)
		{
			assert( current == strList[i] );
			i++;
		}

		assert(i == 3);
	}

	createdTest();

	void nonCircularNodeTest()
	{
		auto node = intList.first;
		assert( node.value == 2 );

		auto prev = node.previous;
		assert(prev is null);

		node = node.next;
		assert( node !is null );
		assert( node.value == 3 );

		node = node.next;
		assert( node !is null );
		assert( node.value == 4 );

		node = node.next;
		assert( node is null );
	}

	nonCircularNodeTest();

	void containsTest()
	{
		assert( intList.contains(3) );
		assert( !intList.contains(5) );
	}

	containsTest();

	void addBeforeAndAfterTest()
	{
		auto node = intList.find(3);
		intList.addAfter(node, new LinkedListNode!(int)(5));
		auto sixNode = intList.addAfter(node, 6);
		auto sevenNode = intList.addBefore(node, 7);
		intList.addBefore(node, new LinkedListNode!(int)(8));

		assert( sixNode.value == 6 );
		assert( sevenNode.value == 7 );

		auto array = [2,7,8,3,6,5,4];
		auto i = 0;
		foreach(current; intList)
		{
			assert(current == array[i]);
			i++;
		}

		for(auto current = intList.first; current !is null; current = current.next)
		{
			assert(current.list is intList);
		}
	}

	addBeforeAndAfterTest();

	void toArrayTest()
	{
		auto values = [2,7,8,3,6,5,4];
		auto array = new int[intList.count];
		intList.toArray(array);

		for(auto i = 0; i < values.length; i++)
		{
			assert( values[i] == array[i] );
		}

	}

	toArrayTest();

	void findTest()
	{
		intList.addFirst(4);
		auto head = intList.find(4);
		auto tail = intList.findLast(4);

		assert( intList.first is head );
		assert( intList.last is tail );
	}

	findTest();

	void removeTest()
	{
		assert( intList.remove(3) );
		assert( intList.count == 7 );

		auto array = [4,2,7,8,6,5,4];
		auto i = 0;
		foreach(current; intList)
		{
			assert(current == array[i++]);
		}

		assert( !intList.remove(9) );

		auto node = stringList.find("you");

		stringList.remove(node);

		assert( node.list is null );
		assert( node.previous is null );
		assert( node.next is null );

		auto strArray = ["I", "love"];
		i = 0;
		foreach(current; intList)
		{
			assert(current == array[i++]);
		}
	}

	removeTest();

	void removeNullNodeTest()
	{
		try
		{
			intList.remove(null);
		}
		catch(Error e)
		{
			assert(true);
		}
	}

	removeNullNodeTest();

	void removeInvalidNodeTest()
	{
		try
		{
			intList.remove(new LinkedListNode!(int)(4));
		}
		catch(Error e)
		{
			assert(true);
		}
	}

	removeInvalidNodeTest();

	void removeFirstAndLastTest()
	{
		stringList.addLast("you");

		stringList.removeFirst();
		stringList.removeLast();

		assert( stringList.count == 1 );
		assert( stringList.first.value == "love" );
	}

	removeFirstAndLastTest();

	void methodOfIListTest()
	{
		stringList.addFirst("I");
		stringList.addLast("you");

		assert( stringList[0] == "I" );
		assert( stringList[1] == "love" );
		assert( stringList[2] == "you" );
		assert( stringList.count == 3 );

		stringList[1] = "hate";

		assert( stringList[1] == "hate" );

		try
		{
			stringList[3] = "Thank";
		}
		catch(Error e)
		{
			assert(true);
		}

		assert( stringList.indexOf("hate") == 1 );
		assert( stringList.indexOf("you") == 2 );

		stringList.removeAt(0);
		stringList.removeAt(1);

		assert( stringList.count == 1 );
		assert( stringList.first.value == "hate" );
		assert( stringList[0] == "hate" );
		assert( stringList.first.next is null );
		assert( stringList.first.theNext is stringList.first );

		stringList.insert(0, "I");
		stringList.insert(1, "love");
		stringList.insert(2, "you");

		assert( stringList[0] == "I" );
		assert( stringList[1] == "love" );
		assert( stringList[2] == "you" );
		assert( stringList.count == 3 );

		try
		{
			stringList.insert(4, "ABCD");
		}
		catch(Error e)
		{
			assert(true);
		}
	}

	methodOfIListTest();

	void clearTest()
	{
		intList.clear();
		assert( intList.count == 0 );
		assert( intList.first is null );
	}

	clearTest();
}